import java.util.Scanner;
public class Test {
    public static void main(String[] args) {
        System.out.println(fib2(20));//这个是从1开始
    }
    public static int fib2(int n){
        if(n == 1||n == 2){
            return 1;
        }
        int f1 = 1;
        int f2 = 2;
        int f3 = 3;
        for(int i = 3 ;i <= n;i++){
            f3=f1+f2;
            f1=f2;
            f2=f3;
        }
        return f3;
    }
    public static int fib1(int n){//斐波拉切//这个是从0开始
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return fib1(n-1)+fib1(n-2);
    }
    public static int sum2(int n){
        if(n>9){
            return n%10+sum2(n/10);
        }
        return n;//注意这个return是return在函数内部
    }
        //写一个递归方法，输入一个非负数字，返回它的每个位之和
    public static int sum(int n){
        if(n==1){
          return 1;
        }
       return n+sum(n-1);
    }
    public static void print2(int n) {
        if(n>9){
            print2(n/10);
        }
        System.out.println(n%10);
    }
    public static void print(int n){
        if(n<10){
            System.out.println(n%10);
            return;
        }//123
        print(n/10);//每次递归在这里结束
        System.out.println(n%10);
    }
    public static void main1(String[] args) {
        //按照顺序打印一个数字的每一位（例如1234打印出1 2 3 4）
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        print(m);
        print(m);
    }
}
